//计算布尔二叉树的值

class Solution {
public:
    bool dfs(TreeNode* root)
    {
        if(root -> left == nullptr)
            return root->val;
        if(root->val == 2)
        {
            return dfs(root->left) | dfs(root->right);
        }
        else 
        {
            return dfs(root->left) & dfs(root->right);
        }
    }
    bool evaluateTree(TreeNode* root) {
        return dfs(root);   
    }

};

//求根节点到叶节点数字之和
class Solution {
public:
    int dfs(TreeNode* root,int x)
    {
        if(root->left == nullptr && root->right == nullptr) return x*10 + root->val;
        x *= 10;
        x += root->val;
        
        if(root->left == nullptr)
        {
            return dfs(root->right,x);
        }
        else if(root->right == nullptr)
        {
            return dfs(root->left,x);
        }
        else 
        {
            return dfs(root->right,x) + dfs(root->left,x);
        }
    }
    int sumNumbers(TreeNode* root) {
         return dfs(root,0);
    }
};

//二叉树剪枝
class Solution {
public:
    TreeNode* dfs(TreeNode* root)
    {
        if(root == nullptr) return root;
        root->left = dfs(root->left);
        root->right = dfs(root->right);
        if(root->left == nullptr && root->right == nullptr)
        {
            if(root->val == 0)
            {
                root = nullptr;
            }
        }
        return root;
    }
    TreeNode* pruneTree(TreeNode* root) {
      return dfs(root);
    }
};

//验证二叉搜索树
class Solution {
public:
    long long preVal = static_cast<long long>(INT_MIN)-1;
    bool isValidBST(TreeNode* root) {
        if(root == nullptr) return true;
        bool left = isValidBST(root->left);
        if(left == false) return false;
        bool cur = false;
        if(root->val > preVal) cur = true;
        preVal = root->val;
        if(cur == false) return false;
        bool right = isValidBST(root->right);
        return left && right;
        
    }
};

//二叉搜索树中第k小的元素
class Solution {
public:
    long long prev = LONG_MIN;
    int t = 0;
    int ret = -1;
    int kthSmallest(TreeNode* root, int k) {
       if(root == nullptr) return -1;
       kthSmallest(root->left,k);
       if(root->val > prev)
       {
           prev = root->val;
           t++;
           if(t == k)
           {
               ret = root->val;
           }
       }
      kthSmallest(root->right,k);
      return ret;
    }
};

//二叉树的所有路径
class Solution {
public:
void dfs(TreeNode* root , string s, vector<string>& ret)
{
    if(root == nullptr) return;
    if(root->left == nullptr && root->right == nullptr)
    {
         s += to_string(root->val);
         ret.push_back(s);
         return;
    }
    s += (to_string(root->val) + "->");
    dfs(root->left,s,ret);
    dfs(root->right,s,ret);
}
    vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> ret;
    string s;
    dfs(root,s,ret);
    return ret;
    }
};

